home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1993
/
Internet Info CD-ROM (Walnut Creek) (1993).iso
/
inet
/
internet-drafts
/
draft-ietf-pip-address-conv-00.txt
< prev
next >
Wrap
Text File
|
1993-06-16
|
48KB
|
1,216 lines
Pip Working Group P. Francis
INTERNET-DRAFT (formerly P. Tsuchiya)
Bellcore
June 1993
Pip Address Conventions
Status of this Memo
This document is an Internet Draft. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its Areas,
and its Working Groups. Note that other groups may also distribute
working documents as Internet Drafts).
Internet Drafts are draft documents valid for a maximum of six
months. Internet Drafts may be Updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet
Drafts as reference material or to cite them other than as a "working
draft" or "work in progress."
Please check the I-D abstract listing contained in each Internet
Draft directory to learn the current status of this or any other
Internet Draft.
Abstract
Pip is an internet protocol intended as the replacement for IP
version 4. Pip is a general purpose internet protocol, designed to
handle all forseeable internet protocol requirements. This
specification is one of a number of documents that specify the
operation of Pip. This specification describes the conventions for
using the various Pip addresses--the hierarchical unicast address,
the class-D style multicast address, the CBT multicast address, and
the nearcast address. This specification does not describe how Pip
addresses are assigned.
Conventions
All functions in this specification are mandatory.
Pip WG, Expires December 1993 [Page 1]
INTERNET-DRAFT Pip Addr Conventions June 1993
1. Introduction
Addressing is the core of any internet architecture. Pip Addresses
are carried in the Routing Directive (RD) of the Pip header (except
for the Pip ID, which in certain circumstances functions as part of
the Pip Address). Pip Addresses are used only for routing packets.
They do not identify the source and destination of a Pip packet. The
Pip ID does this. This memo describes the various Pip addressing
types.
There are four Pip Address types [2]. The hierarchical Pip Address
(referred to simply as the Pip Address) is used for scalable unicast
and for the unicast part of a CBT-style multicast and nearcast. The
multicast part of a CBT-style multicast is the second Pip address
type. The third Pip address type is class-D style multicast. The
fourth type of Pip address is the so-called "nearcast" address. This
address causes the packet to be forwarded to one of a class of desti-
nations (such as, to the nearest DNS server).
Bits 0 and 1 of the RC for the near-term Pip architecture indicate
which of four address families the FTIFs and Dest ID apply to. The
values are:
Value Address Family
----- --------------
00 Hierarchical Unicast Pip Address
01 Class D Style Multicast Address
10 CBT Style Multicast Address
11 Nearcast Pip Address
The remaining bits are defined differently for different address fam-
ilies, and are defined in the following sections. The RC Contents
value associated with this RC definition is 1.
2. Hierarchical Unicast Pip Addresses
2.1. General
Pip Addresses are hierarchical addresses. Pip Addresses are assigned
such that a number at any level of the hierarchy is unique only with
Pip WG, Expires December 1993 [Page 2]
INTERNET-DRAFT Pip Addr Conventions June 1993
respect to the levels above it. Because of this, all Pip Address are
unique.
While the sole purpose of the Pip Address is to encode topologically
significant addresses, the Pip Address does also represent a hierar-
chy of Pip Address Assignment Authorities (PAAA). At the top of the
PAAA hierarchy is the root PAAA. This PAAA assigns top-level Pip
Address numbers. These numbers appear at the top of any fully-
enumerated Pip Address. (By fully-enumerated, we mean a Pip Address
where all levels of the address are given.)
Pip Addresses signify either the location of a Pip system (host or
router), or a subnetwork. In the latter case, the Pip ID is used to
route a Pip packet to a Pip system across the subnetwork. Thus, a
Pip Address or a Pip Address+ID causes a Pip packet to be routed to
the Pip processing module of a given Pip system, after which the Pro-
tocol field of the Pip header is used for further demultiplexing.
(This having been said, the extension of a Pip Address on the least
significant end to signify sub-system entities, such as processors
within a multi-process host, or peripherals such as a screen or disk,
is possible. Such use is a local matter--it does not effect Pip
routing outside the host. Such use is outside the scope of this
specification.)
2.2. Routing Context (RC) Structure
When the RC Contents field is 1, bits 0 and 1 of the Routing Context
(RC) indicate the address family. If the address family is Pip
Hierarchical Unicast Address, then bits 0 and 1 are value 00. When
this RC indicates Pip Hierarchical Unicast Address (called simply the
Pip Address in this document), the RC is structured as follows:
bits meaning
---- -------
0,1 address family (= 00)
2,3 level
4,5 metalevel
6 exit routing type
This document discusses the conventions for handling Pip Addresses
and their related Routing Context.
Pip WG, Expires December 1993 [Page 3]
INTERNET-DRAFT Pip Addr Conventions June 1993
2.3. Pip Addresses in the Pip Header
The Pip header carries Pip Addresses as a sequence of FTIFs (Forward-
ing Table Index Fields). Each FTIF is 16 bits in length. Usually,
each FTIF represents one layer of the hierarchy, although it is pos-
sible for a single hierarchy layer to span multiple 16-bit FTIFs.
The sequence of FTIFs is called the FTIF Chain.
Both the source and destination Pip Addresses are carried in the same
FTIF Chain. The source Pip Address comes first, and is written in
order of lowest hierarchy level first. The destination Pip Address
follows, and is written in order of highest hierarchy level first.
Note that, depending on the locations of source and destination rela-
tive to each other, it is not always necessary to include the top
levels of the Pip Address in the FTIF Chain.
The least significant bits of each FTIF is the relator. The three
relator types are:
value type
----- ----
last bit = 0 horizontal
last 5 bits = 11111 extension
all others vertical
The relator indicates what the relationship between the current and
subsequent FTIF is. Horizontal indicates that the subsequent FTIF is
a separate Pip Address number, but that the number is neither
hierarchically above nor below the current one. Vertical indicates
that the subsequent FTIF is a separate Pip Address number, and that
number is hierarchically above or below the current one. Extension
indicates that the subsequent FTIF is part of the same Pip Address
number.
When a Pip Address number is greater than 15 bits in length, then the
extension must be used to encode the number. When an extension is
used, the Pip Address number is right-justified. For instance, if
the Pip address number (without the relator) is hex 89ab, and the
subsequent number is below it, then it is written as 3f,1357 The last
bit of "1357" is neither "0" nor "11111", which means vertical. The
last five bits of "3f" are "11111", which means extension. The
extension is needed because the vertical relator caused the number to
be 17 bits long, thus forcing the extension.
The reason for using five bits to encode extension and one bit to
Pip WG, Expires December 1993 [Page 4]
INTERNET-DRAFT Pip Addr Conventions June 1993
encode horizontal and vertical is to 1) maximize the code space
available for horizontal and vertical use (each type gets roughly 1/2
the code space), and 2) maximize the use of forwarding table memory
for the common case of direct index into the forwarding table. If we
used 2 bits to encode all three relators, then vertical and horizon-
tal would each get only 1/4 of the available code space. The reason
we five bits rather than, say, 4 or 6, is that a 5 bit relator allows
48 bit numbers to be encoded in 4 16-bit FTIFs (rather than 5 FTIFs
as would be the case with a 6 bit relator), while still allowing 64
bit numbers to be encoded in 6 FTIFs (as would also be the case with
a 4 bit relator).
Any Pip Address number is limited in size to 64 bits. This allows a
Pip ID to be used as a Pip Address number if desired. When a single
64-bit Pip Address number is notated, it consists of 6 FTIFs. The
first five have 5-bit extension relators. The sixth has the "true"
relator, which may be vertical or horizontal, depending on the con-
text of the number.
2.4. Assignment of Pip Addresses
The root PAAA assigns top-level Pip Address numbers to two types of
entities--providers and private networks. (Note that in this paper,
a "private network" is often referred to as a "subscriber network" to
indicate its role as a subscriber of network services from a pro-
vider.) Pip Addresses with a provider at the top-level are called
provider-rooted Pip Addresses. Pip Addresses with a private network
at the top-level are called private-rooted Pip Addresses.
The purpose of assigning numbers to providers is to allow good scal-
ing characteristics at the top level of routing (because only routes
to top level providers need be calculated), and to allow for policy
routing, particularly provider selection.
The purpose of assigning numbers to private networks is to give the
systems in the private network globally unique Pip Addresses that are
not dependent on the private network's service provider. The top-
level private network numbers are not advertised outside of the
private network, and except for intra-private network communications,
and even then only rarely, never appear in Pip headers. Top-level
private network numbers are primarily used to allow hosts to deter-
mine when another host is in the same private network [9].
Pip WG, Expires December 1993 [Page 5]
INTERNET-DRAFT Pip Addr Conventions June 1993
A Pip Address consists of zero or more Pip Address numbers with hor-
izontal relators, followed by one or more Pip Address numbers with
vertical relators, and ending with zero or one Pip Address numbers
with a horizontal relator.
The zero or more initial horizontal numbers represent a "route frag-
ment". Horizontal numbers are used when 1) the "top" of a Pip
Address (the first vertical number, representing a provider) is not
advertised globally, and so another provider that is must be
prepended to the Pip Address, or 2) the top of the Pip Address is
advertised globally, but an adjacent provider represents a meaningful
policy choice. (The top-level number of a private-rooted Pip Address
always has a vertical relator.)
For example, consider the following topology:
other other
big---BP1------BP2---big
providers \ / providers
\ /
\ /
LAP (local access provider)
|
|
+---------------------+
| | | Sub1
| Area1----Area2 | (subscriber network)
| |
+---------------------+
Here we have a subscriber network (Sub1) connected to a local access
provider (LAP), which is in turn connected to two Big Providers (BP1
and BP2). Because LAP is a provider, it has a top-level number.
But, because LAP is only a local access provider, let's assume that
it is not advertised outside of BP1 or BP2. Thus, the Pip Addresses
of a subscriber host in Area1 are:
BP1(hor),LAP(ver),Sub1(ver),Area1(hor)
BP2(hor),LAP(ver),Sub1(ver),Area1(hor)
Note that Pip Addresses are rooted at providers. Issues concerning
provider-rooted addresses are discussed in [2] and [3]. These
addresses would be advertised by DNS and carried in the FTIF Chain.
Because BP1 or BP2 is advertised globally, packets from anywhere
would reach BP1 or BP2. BP1 and BP2 know how to route to LAP, which
Pip WG, Expires December 1993 [Page 6]
INTERNET-DRAFT Pip Addr Conventions June 1993
knows how to route to Sub1, and so on.
2.5. Hierarchy Levels in Pip Addresses
One reason that forwarding is fast with Pip is that the entire Pip
Address does not have to be processed upon reception of a Pip packet.
Rather, a router can just look at the relevant FTIF and forward the
packet. To understand the appropriate context in which to interpret
the FTIF, however, the Routing Context (RC) must be examined. The
RC, among other things, contains information about the hierarchy
level of the FTIF. This is necessary because it is possible for a
given FTIF value to exist at any level of the hierarchy, and it is
possible for a router to be operating at multiple levels of the
hierarchy.
Generally speaking, the level sub-field in the Routing Context (RC)
is 0 for the highest level, and counts up one for each level deeper
in the hierarchy. So, the top level of the hierarchy is level 0, the
next level below that level 1, and so on. However, level alone is
not enough to always determine the context of an FTIF. The following
paragraphs explain why this is so.
One of the goals of Pip is to isolate intra-domain (subscriber net-
work) addressing from inter-domain (provider network) addressing con-
ventions. The better we can isolate these two parts of the address,
the better we can deal with address prefix changes, such as those
that result from changing providers. (Note that, in the above exam-
ple, BP1.LAP.Sub1 and BP2.LAP.Sub1 constitute the provider part of
the addresses, and Area1 constitutes the subscriber part.)
One of the techniques used to isolate subscriber and provider address
parts is to allow the source and destination addresses of intra-
domain packets (that is, packets between two hosts in the same sub-
scriber network) to not encode the provider parts at all. In the
context of the above example, this means that the FTIF Chain would
not contain BP1.LAP.Sub1. Instead, it would contain only the Area1
part. By not requiring the provider part of the address to be in
intra-domain packets, we allow network administrators to assign
addresses internally without regard to the provider part. For
instance, in the subscriber network the administrator should be able
to assign numbers to Area1 and Area2 without concern for what pro-
vider prefixes it has or may have in the future.
Pip WG, Expires December 1993 [Page 7]
INTERNET-DRAFT Pip Addr Conventions June 1993
In order to do this, the administrator must not only be isolated from
the value of the provider prefix, but also from the number of levels
in the provider prefix. But, the level is needed by subscriber
routers to know how to forward based on examination of a single FTIF.
Therefore, level alone is not enough to determine the context of an
FTIF. To see why this is so, consider the following example:
----BP1--------BP2----
| |
| |
+---------------------+
| | | | Sub1
| Area1--R1--Area2 | (subscriber network)
| | | |
| subArea2 |
| |
+---------------------+
Here we have a subscriber network (Sub1) attached to two providers
(BP1 and BP2) at two internal areas (Area1 and Area2 respectively).
Area2 has a another layer of hierarchy below it (subArea2). Attached
to Area1, Area2, and subArea2 is a router R1. Assume that the prefix
given to Sub1 from BP1 is 1-2-3, and the prefix given to Sub2 from
BP2 is 2-3. In other words, the top-level number of BP1 is 1 and the
top-level number given to BP2 is 2. Both BP1 and BP2 have assigned
the number 3 to Sub1. However, BP1 has an internal level of hierar-
chy whereas BP2 does not. Thus, BP1's prefix has three numbers while
BP2's prefix has only two.
Assume further that Area1 is assigned the number 2, Area2 is assigned
the number 3, and subArea2 is assigned the number 2. Thus, the Pip
Addresses for hosts in Area1 are:
1-2-3-2
2-3-2
and the Pip Addresses for hosts in subArea2 are:
1-2-3-3-2
2-3-3-2
(Note that these Pip Addresses are not notated properly. For the
sake of simplicity, the relator bits are not shown in this example.)
Now, assume that we try to use level alone to indicate the appropri-
ate hierarchy level in the RC field. Assume that router R1 receives
a packet with level=3 and FTIF=2 (where level=0 is the top level).
Router R1 cannot determine if this packet is for something in Area1
Pip WG, Expires December 1993 [Page 8]
INTERNET-DRAFT Pip Addr Conventions June 1993
(1-2-3-2), or subArea2 (2-3-3-2). Both can have FTIF=2 at level=3,
depending on which provider address is used. Note that if the router
parses the address from the top level down, it could resolve the
ambiguity. However, this both results in a slower lookup, and weak-
ens the isolation between provider and subscriber addressing (even
internal packets would have to carry full addresses).
To fix this ambiguity, and still allow for provider and subscriber
address isolation, we introduce a second subfield into the RC, the
metalevel field. Whereas there is a level boundary at every level of
the hierarchy, there is a metalevel boundary only at those hierarchy
boundaries where there is a reasonable probability that the hierarchy
element will have multiple parents. This will normally be the case
at significant administrative boundaries. (Note that horizontal
administrative boundaries do not represent metalevel boundaries.
Metalevel boundaries, like level boundaries, indicate different
hierarchical levels.)
The most significant metalevel boundary is that between provider and
subscriber. Every provider/subscriber boundary must also be a
metalevel boundary. There may be metalevel boundaries at lower lev-
els in the hierarchy. There may not be metalevel boundaries above
the provider/subscriber metalevel boundary.
Metalevel numbering in the RC is similar to level numbering it that
the highest metalevel is metalevel=0, the next lower metalevel boun-
dary is metalevel=1, and so on. Level numbering starts over again at
0 at each metalevel boundary. Thus, the top-level of the hierarchy
(the level at which the root PAAA assigns Pip numbers) is
metalevel=0, level=0. The next level down (if it is not at the
provider/subscriber boundary) is metalevel=0, level=1. This level
could, for instance, be a hierarchy level within the provider to
allow for better scaling in the provider network. This numbering
continues for all additional levels above the provider/subscriber
boundary (that is, metalevel=0, level=2; metalevel=0, level=3, and so
on).
At the provider/subscriber boundary, the metalevel is incremented and
the level reset to 0. Thus, the level just below the
provider/subscriber boundary is metalevel=1, level=0. The next level
down is metalevel=1, level=1, and so on. Thus, a packet between two
hosts in the same subscriber network is transmitted at metalevel=1,
level=0, regardless of the provider prefixes owned by those two
hosts. This allows "hard-coded" configuration of Pip Addresses for
intra-subscriber destinations. (By hard-coded, I mean static
Pip WG, Expires December 1993 [Page 9]
INTERNET-DRAFT Pip Addr Conventions June 1993
configuration of a Pip Address in a computer such that the Pip
Address is not subject to auto-configuration protocols. An example
of this is to put a Pip Address in an ASCII configuration file used
by an application.) It also allows a private network to operate
without connecting to any providers at all. When such a private net-
work connects to a provider, it can then obtain one or more provider
prefixes.
Note that it is not a good idea to "hard-code" Pip Addresses with the
private-rooted address prefix, because even these prefixes are sub-
ject to change, for instance when two private networks merge.
2.6. Pip Address Notation
This section describes how to notate a Pip Address (for instance, in
an ASCII file). There is only one way to notate a Pip Address. Pip
Address notation closely resembles the encoding of a Pip Address in a
Pip header.
The Pip Address is notated as a series of hex numbers separated by
commas (",") and dots ("."). Each hex number can be between one and
four digits in length. Up to four digits are needed to encode a 16-
bit FTIF. The relators, including the extension relator, are
included in the hex number.
When notating a Pip Address, a comma is used at address positions
where a metalevel boundary exists. A dot is used otherwise.
When notating a Pip Address, the left-most (high-order, or higher-
in-the-hierarchy) hex number must be at a metalevel boundary, and
must be a level=0 Pip Address number. Leading commas are used to
indicate the metalevel boundary of the Pip Address. A Pip Address
notated from the root of the Pip Address hierarchy (metalevel=0) has
no leading commas. A Pip Address notated from the top of the private
network portion of the Pip Address hierarchy (metalevel=1) has a sin-
gle leading comma. A Pip Address rooted at metalevel=2 has two lead-
ing commas, and a Pip Address rooted at metalevel=3 has three leading
commas. The maximum number of metalevels is four (encoded as two
bits in the RC).
The following network is used to illustrate Pip Address notation.
BP1 and BP2 are big providers that are advertised globally by the
routing protocol. LAP is a local access provider that is not
Pip WG, Expires December 1993 [Page 10]
INTERNET-DRAFT Pip Addr Conventions June 1993
advertised globally. Sub1 is the subscriber network. Area1 and
Area2 are areas inside the subscriber network. subArea2 is an area
within Area2. There is a single metalevel boundary--between the sub-
scriber network Sub1 and the providers, LAP and BP2.
---BP1----LAP--------BP2----
| |
| |
+---------------------+
| | | | Sub1
| Area1------Area2 | (subscriber network)
| | |
| subArea2 |
| |
+---------------------+
Assume the following Pip Address number assignments:
network assignment
component # ( << 1) notes
--------- ---------- -----
BP1 23 (46) top-level number
BP2 9a (134) top-level number
LAP 1b9 (372) top-level number
Sub1 493aa (92754) top-level number
LAP/Sub1 43 (86) assigned to Sub1 by LAP PAAA
BP2/Sub1 11a (234) assigned to Sub1 by BP2 PAAA
Area1 b3 (166) assigned by Sub1 PAAA
Area2 71 (e2) assigned by Sub1 PAAA
Area2/subArea2 14 (28) assigned by Area2 PAAA
Note that none of the numbers shown above include the relator. The
number in parenthesis is the assigned number left shifted one. This
is shown to more clearly indicate the number with the relator
appended.
A host in Area1 may have the following four Pip Addresses:
Pip Address PAAA Hierarchy
----------- --------------
1. 46.373.87,166 root.BP1.LAP.Sub1,Area1
2. 135.235,166 root.BP2.Sub1,Area1
3. 13f.2755,166 root.Sub1,Area1
4. ,166 private,Area1
Pip WG, Expires December 1993 [Page 11]
INTERNET-DRAFT Pip Addr Conventions June 1993
The first two Pip Addresses are provider-rooted. These would be used
by hosts in other private networks to reach the host in Area1. Note
that the last bit of the first number of Pip Address 1 has a 0 as the
least significant bit. This indicates a relator of horizontal.
Since LAP has a top-level Pip Address number, it is not "under" BP1
in the address hierarchy. Never-the-less, BP1 is in the Pip Address
as part of a route fragment either because LAP isn't advertised glo-
bally by routing, or because being able to route paths through BP1 is
important to hosts in Sub1.
The third Pip Address is private-rooted. This address would not be
used by hosts outside of Sub1 to address hosts inside Area1, because
Sub1 is not advertised globally. The third Pip Address would, how-
ever, be advertised by DNS. This would allow other hosts in Sub1 to
determine that the Area1 host was in the same private network (and
thus, no provider prefix is needed to address the packet).
The fourth Pip Address is not globally unique, and can only be used
locally. The leading comma indicates that the top level of this
address is at metalevel=1. Thus, if a host creates a Pip header
using the fourth Pip Address, it would know to set the metalevel sub-
field in the RC field to 1. The fourth Pip Address would not be
advertised in DNS.
2.7. Router Addressing Conventions
A router plays several roles. First, it can of course receive Pip
packets to be forwarded to another router or a host. Second, as the
destination of Pip packets, it can itself be a host. Third, it can
be the "target" of a Pip packet that must then be translated into an
IP packet and forwarded. We use the term "target" rather than sink
to indicate that, even though the FTIF Chain is structured to deliver
the packet to the router, the router is not the ultimate destination
of the packet. Fourth, the router can be the end of a tunnel, in
which case it is the target of a Pip packet that is untunneled and
forwarded.
Thus, routers can be the targets of three kinds of packets-- those
meant for it, those that need to be translated, and those that need
to be untunneled. To distinguish between these three types, routers
must have a different Pip Address for each type. In its role as a
host, the router uses the Pip Address of the attached LAN if there is
one, or simply the destination Pip Address assigned to the router if
Pip WG, Expires December 1993 [Page 12]
INTERNET-DRAFT Pip Addr Conventions June 1993
there isn't.
If the router is a target system either as a tunnel endpoint or for
translation, then it must have distinct Pip Addresses for each of
these cases. These Pip Addresses may or may not be interface
specific, depending on the situation. Normally these Pip Addresses
will all be identical except for the lowest FTIF. The exception to
this rule is when the router is a border router.
When a router is a Pip/IP translator, then it is a translator for a
set of IP destinations. When a DNS lookup for one of these IP desti-
nations is made, the Pip Address representing the router's role as a
translator is returned (along with the router's Pip ID).
In the case where the router is a tunnel endpoint, the Pip Address
assigned for the purpose must be advertised to the router's peer tun-
nel endpoints. When the router is the entry point of a tunnel, it
puts this Pip Address in the source address location of the FTIF
Chain of the Transit Part that it creates for the tunnel.
When a Pip router inside a tunnel cannot deliver the packet to the
tunnel exit router, it sends a PCMP error message back to either the
source host or the tunnel entry router, depending on the cir-
cumstances [5]. In the former case, the returned Pip packet is tar-
geted to the original tunnel entry router, which becomes the tunnel
exit router. In this case, the router untunnels the packet and for-
wards it on. In the latter case, the tunnel entry router becomes the
actual destination of the PCMP message.
Because the tunnel endpoint router must be able to distinguish
between being the tunnel exit system and being the recipient of the
returned PCMP message, there must be a means by which the router that
initiated the PCMP message can indicate the distinction. To do this,
we use the following convention.
When a tunnel endpoint is to untunnel a packet and forward it on, the
relator of the last FTIF indicates horizontal. When a tunnel end-
point is the recipient of a packet (that uses the router's tunnel Pip
Address), the relator of the last FTIF indicates vertical.
2.8. Host Addressing Conventions
Host Pip Addresses may be either LAN-based or host-based. In the
Pip WG, Expires December 1993 [Page 13]
INTERNET-DRAFT Pip Addr Conventions June 1993
former case, the host uses as its Pip Address the Pip Address of its
attached LAN. (If there are multiple attached LANs, the host has
multiple Pip Addresses.) The host's Pip ID is used to deliver the
packet from a router (or another host) on the LAN to the host. That
is, the Pip ID in the Dest ID field of the Pip header is examined to
determine the appropriate LAN address to forward the packet to. If
necessary, the Pip ID is also used to ARP for the destination host's
LAN address.
In the latter case (host-based), the FTIF Chain is sufficient to
deliver the packet to the destination host. If the host is using
host-based addressing, but is also attached to a LAN, then the host
could have a Pip Address prefix that matches the LAN Pip Address.
This address prefix would be followed by one or more FTIFs.
In order for a router to distinguish between LAN-based and host-based
Pip Addresses for hosts on its attached LAN, we use the following
convention. If the host is using LAN-based addressing, then the FTIF
representing the LAN (in this case, the last FTIF) has a horizontal
relator. If the host is using host-based addressing, then the FTIF
representing the LAN (in this case, not the last FTIF) has a vertical
relator.
2.9. Reversing an FTIF Chain with Pip Addresses
There are two cases where a Pip system may want to "reverse" an FTIF
Chain with Pip Address. Reversing an FTIF Chain is the process of
creating a new FTIF Chain that allows the packet to get back to the
source host. The first case is that of a destination host returning
a packet to the source host. The second case is that of a router
returning a PCMP message back to the source host or a tunnel entry
system.
In the following descriptions, we assume that an FTIF Chain of the
following form is received:
Pip WG, Expires December 1993 [Page 14]
INTERNET-DRAFT Pip Addr Conventions June 1993
V1 V2...Vi H1...Hj Hj+1...Hj+k Hj+k+1...Hj+k+m V1 V2... Vn
| | | |
| | policy | |
| source address | route | dest address |
i >= 0, j >= 1, k >= 0, m >= 0, n >= 1
That is, the FTIF Chain starts with a source address that contains
zero or more vertical FTIFs followed by at least one horizontal FTIF.
This is followed by 0 or more horizontal FTIFs that make up the "pol-
icy route". This is in turn followed by the destination address,
made up of 0 or more horizontal FTIFs followed by one or more verti-
cal FTIFs. (There is one exception to the dest address shown here,
which is that in the case of returning a Pip packet to a tunnel entry
point, the final FTIF may be horizontal.)
2.9.1. Host FTIF Chain Reversal
To reverse an FTIF Chain, the host first extracts the destination Pip
Address from the received FTIF Chain. The destination Pip Address
can be determined by matching the trailing FTIFs against those of the
host's own addresses. That is, FTIF Vn is compared against the
host's lowest level address component, Vn-1 against the host's next
lowest level address component, and so on.
Note that the destination Pip Address may be a partial address, com-
ing under a metalevel boundary. In this case, there would be no hor-
izontal components in the destination address of the received FTIF
Chain. The destination Pip Address of the received FTIF Chain must
be one of the Pip Addresses of the host. This becomes the source Pip
Address of the returned (reversed) Pip packet.
The host then takes the remainder of the FTIF Chain and treats it as
the destination Pip Address of the returned Pip packet. Note that
the remainder of the FTIF Chain may in fact be more than the received
source Pip Address, for instance because of the inclusion of a policy
route in the FTIF Chain. From the perspective of the reversing host,
however, this does not change things.
At this point, the host has the source and "destination" Pip
Addresses for the return Pip packet. The host sets the Active FTIF
Pip WG, Expires December 1993 [Page 15]
INTERNET-DRAFT Pip Addr Conventions June 1993
field, and the level, metalevel, and exit routing type subfields of
the RC, according to the procedures described in [9].
2.9.2. Router FTIF Chain Reversal
To reverse an FTIF Chain, a router must first decide how much of the
received source Pip Address is needed to return the packet. For
instance, if the packet is destined to an inter-domain location, but
has not yet left the private network, then only the private network
part of the address (metalevel=1 cluster) is needed.
There are three cases to handle;
1. The packet is in the source's metalevel>0 cluster,
2. The packet is at metalevel=0,
3. The packet is in the destination's metalevel>0 cluster
The first case exists when the prefix of the source address in the
received FTIF Chain matches one of those of the router's. Since the
received FTIF Chain does not explicitly indicate which FTIFs consti-
tute the source address, the router must compare prefixes by first
finding the first horizontal FTIF of the FTIF Chain (H1). If this
matches the lowest horizontal FTIF in one or more of the router's Pip
Addresses (that is, the FTIF in the router's Pip Address correspond-
ing to H1), then the router compares the FTIFs in its Pip Address
corresponding to H2 through Hj against H2 through Hj in the received
FTIF Chain, and the FTIFs in its Pip Address corresponding to Vi,
Vi-1, and so on down to the metalevel boundary, against those in the
received FTIF Chain.
If all of these FTIFs match, then the router is in the same
metalevel>0 cluster as the source, and does not need to include the
common prefix in the return packet. That is, the series of FTIFs
starting from the first FTIF and going up to the FTIF previous to the
common prefix is considered to be the "source address" of the
received FTIF Chain.
If any of these FTIFs don't match, then the router considers the
"potential source address" of the received FTIF Chain to be the
series of FTIFs starting from the first FTIF and going up to the FTIF
previous to the Active FTIF. If one of the horizontal FTIFs of the
Pip WG, Expires December 1993 [Page 16]
INTERNET-DRAFT Pip Addr Conventions June 1993
potential source address matches that of the router's provider net-
work, then that FTIF and all subsequent FTIFs are stripped from the
potential source address, and what remains is considered to be the
"source address" of the received FTIF. (Note that this may not be
the complete source address of the source host, but it is sufficient
to route the packet back to the source host.)
The series of FTIFs that are considered to be the source address of
the received FTIF Chain are reversed and used as the destination
address of the FTIF Chain of the return packet. The router then
chooses one of its own Pip Addresses to be the source address in the
return packet. Then the router creates an FTIF Chain, Active FTIF
field, and level, metalevel, and exit routing type subfields of the
RC according to the algorithm for host creation of a Pip header
described above.
2.9.3. Reversal of Multiple FTIF Chains (Tunneling Case)
If there are multiple FTIF Chains in the received Pip packet, then
all of them must be reversed in the return Pip packet. Each indivi-
dual FTIF Chain is reversed according to the rules stated above. The
order of encapsulation in the returned packet is the same as the
received packet.
3. CBT Style Multicast Addresses
When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 10,
the FTIF and Dest ID indicate CBT (Core Based Tree) style multicast.
The remainder of the bits are defined as follows:
bits meaning
---- -------
0,1 CBT Multicast (= 10)
2,3 level
4,5 metalevel
6 exit routing type
7 on-tree bit
8,9 scoping
With CBT (Core-based Tree) multicast, there is a single multicast
Pip WG, Expires December 1993 [Page 17]
INTERNET-DRAFT Pip Addr Conventions June 1993
tree connecting the members (recipients) of the multicast group (as
opposed to Class-D style multicast, where there is a tree per
source). The tree emanates from a single "core" router. To transmit
to the group, a packet is routed towards the core using unicast rout-
ing. Once the packet reaches a router on the tree, it is multicast
using a group ID.
The FTIF Chain for CBT multicast contains the (unicast) Hierarchical
Pip Address of the core router and the Pip Address of the source.
The Dest ID field contains the group ID.
A Pip CBT packet, then, has two phases of forwarding, a unicast phase
and a multicast phase. The "on-tree" bit of the RC indicates which
phase the packet is in. While in the unicast phase, the on-tree bit
is set to 0, and the packet is forwarded as for Pip Addresses as
described above. During this phase, the scoping bits are ignored.
If during this phase the packet cannot be delivered, the PCMP Packet
Not Delivered (PND) message is sent as though the original packet
were a Pip Address.
Once the packet reaches the multicast tree, it switches to multicast
routing by changing the on-tree bit to 1 and using the Dest ID group
address for forwarding. During this phase, bits 2-6 of the RC are
ignored. PCMP messages are not sent in response to a packet in the
on-tree phase of CBT multicast.
The CBT specification [7] describes the forwarding of CBT packets for
IP. For use with Pip, the CBT specification is used as is, with the
following exceptions:
1. The source and destination Pip Addresses in the FTIF Chain take
on the roles of the source and destination IP address, with the
proviso that the packet is forwarded according to Pip Address
forwarding rules.
2. The on-tree bit in the RC takes on the role of the on-tree bit
in the CBT IP option.
3. The Dest ID of the Pip header takes on the role of the group ID
in the CBT IP option.
4. The scoping bits in the RC take on the role of the scoping bits
in the CBT IP option.
Pip WG, Expires December 1993 [Page 18]
INTERNET-DRAFT Pip Addr Conventions June 1993
4. Class D Style Multicast Addresses
When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 01,
the FTIF and Dest ID indicate Class D style multicast. The remainder
of the RC is defined as:
bits meaning
---- -------
0,1 Class D Style Multicast (= 01)
2,3 scoping
By "class D" style multicast, we mean multicast using the algorithms
developed for use with Class D addresses in IP (class D addresses are
not used per se). This style of routing uses both source and desti-
nation information to route the packet (source host address and des-
tination multicast group).
For Pip, the FTIF Chain holds the source Pip Address, in order of
most significant hierarchy level first. The reason for putting the
source Pip Address rather than the Source ID in the FTIF Chain is
that use of the source Pip Address allows the multicast routing to
take advantage of the hierarchical source address, as is being done
with IP.
The Dest ID field holds the multicast group. All of the existing IP
Class D multicast addresses are used with Pip by virtue of the "local
IP" Pip ID address space [8]. These addresses are necessary when a
multicast group is partly Pip and partly IP. For a pure Pip multi-
cast group, either an IP Class D multicast address can be used, or
another (non-IP) Pip address.
To forward a Class D multicast packet, a router first examines the
FTIF Chain starting from the beginning (Active FTIF field = 1).
FTIFs are examined in order until the source of the packet is unambi-
guously determined. Note that the FTIF Chain only identifies the
source subnet, not the source host. This is adequate to describe the
multicast tree, since all trees coming from hosts on the same subnet
will be identical.
Bits 2 and 3 of the RC are the scoping bits. The use of these bits
are for further study. As of this writing, there is no specification
for a routing algorithm to create Class D style multicast trees with
Pip. It is expected that such a specification will be written in the
future.
Pip WG, Expires December 1993 [Page 19]
INTERNET-DRAFT Pip Addr Conventions June 1993
4.1. Nearcast Addressing
Nearcast addressing is a new form of addressing that, for now, is
peculiar to Pip. Nearcast addressing causes a packet to be routed to
one (the "nearest") of a group of systems. Thus, nearcast is similar
to multicast in that a nearcast address identifies a group of sys-
tems. Nearcast is similar to unicast, however, in that it only
delivers one packet. To do nearcast addressing, the (other unicast)
routing algorithm must maintain a route to the nearest member of each
nearcast group.
Nearcast is particularly useful for discovery applications. It
allows one of a class of systems to be found without prior knowledge
of that system's unicast address. Pip uses nearcast to help auto-
configure Pip hosts.
When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 11,
the FTIF and Dest ID indicate Nearcast addressing. The remainder of
the RC is defined as:
bits meaning
---- -------
0,1 Nearcast Address (= 11)
2,3 level
4,5 metalevel
6 exit routing type
7 nearcast active
8,9 scoping
With nearcast routing, the packet is unicast, but to the nearest of a
group of destinations. This type of routing is used by Pip for auto-
configuration. Other applications, such as discovery protocols, may
also use nearcast routing.
Like CBT, Pip nearcast has two phases of operation, in this case the
unicast phase and the nearcast phase. The unicast phase is for the
purpose of getting the packet into a certain vicinity. The nearcast
phase is to forward the packet to the nearest of a group of destina-
tions in that vicinity.
Thus, the RC has both unicast and nearcast information in it. During
the unicast phase, the nearcast active bit is set to 0, and the
packet is forwarded according to the rules of Pip Addressing. The
scoping bits are ignored.
Pip WG, Expires December 1993 [Page 20]
INTERNET-DRAFT Pip Addr Conventions June 1993
The switch from the unicast phase to the nearcast phase is triggered
by the presence of an FTIF of value 1 in the FTIF Chain. When this
FTIF is reached, the nearcast active bit is set to 1, the scoping
bits take effect, and bits 2 through 6 are ignored. When in the
nearcast phase, forwarding is based on the Dest ID field.
References
[1] Francis, "Pip Header Processing", Internet-Draft
[2] Francis, "Pip Near-term Architecture", Internet-Draft
[3] Francis, "On the Assignment of Provider-rooted Addresses",
Internet-Draft
[4] Thomson, Francis, "Use of DNS with Pip", Internet-Draft
[5] Francis, Govindan, "PCMP: Pip Control Message Protocol",
Internet-Draft
[6] Pip ARP (to be completed)
[7] Ballardie, Francis, Crowcroft, "Core Based Trees (CBT), An
Architecture for Scalable Inter-Domain Multicast Routing",
Internet-draft.
[8] Francis, "Pip Identifiers", Internet-Draft
[9] Francis, "Pip Host Operation", Internet-Draft
Pip WG, Expires December 1993 [Page 21]